package com.heima.leetcode.practice;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * @author 勾新杰
 * @version 1.0
 * @description: leetcode 56 合并区间
 * @date 2024/12/19 11:09
 */
public class E56 {

    /**
     * 合并区间
     * @param intervals 区间数组
     * @return 合并后的区间数组
     */
    public int[][] merge(int[][] intervals) {
        // 1. 边界条件
        if (intervals.length <= 1) return intervals;
        // 2. 按照左边界升序排序
        Arrays.sort(intervals, Comparator.comparingInt(arr -> arr[0]));
        // 3. 创建一个结果集，将第一个区间添加进去
        List<int[]> result = new ArrayList<>();
        result.add(intervals[0]);
        // 4. 遍历区间数组，判断是否需要合并，需要则合并，否则添加
        for (int i = 1; i < intervals.length; i++) {
            int[] current = intervals[i];
            int[] last = result.get(result.size() - 1);
            if (current[0] <= last[1]) last[1] = Math.max(last[1], current[1]);
            else result.add(current);
        }
        // 5. 返回结果集
        return result.toArray(new int[result.size()][]);
    }
}
